/*题目描述：leetcode111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

*/

//递归法
/*需要注意的是叶结点的定义，
如果一个树的根只有左子树，并不意味着其最小深度是1，因为左子树并没有叶节点，
所以此时的最小深度需要根据右子树的叶节点求
*/
class Solution {
public:
    int minDepth(TreeNode* root) {
        // 根节点为空直接返回
        if(root == nullptr) return 0;
        // 分别求出左右子树的最小深度
        int leftDepth = minDepth(root->left);
        int rightDepth = minDepth(root->right);
        // 处理左右子树其中一个为空的情况
        // 其中一个为空则根据另一个求最小深度
        if(root->left && root->right == nullptr)
            return  1+leftDepth;
        if(root->left == nullptr && root->right)
            return 1+rightDepth;
        // 两个子树同时为空或者同时不为空的时候
        // 只有两棵子树同时为空才是满足条件的最小深度的叶节点
        int res = 1+min(leftDepth,rightDepth);
        return res;
    }
};

//递归法
/*需要注意的是叶结点的定义，
类似最大深度的求法，此题也可以使用层次遍历来实现
但是此时的层次遍历有了提前终止条件，那就是碰到一个叶节点。
*/

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        queue<TreeNode*> que;
        que.push(root);
        // 最小深度初始化
        int depth = 0;
        // 与普通层次遍历类似
        while(!que.empty()){
            TreeNode* node;
            size_t size = que.size();
            depth++;
            while(size--){
                node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right); 
                // 如果碰到叶节点，则说明是最小深度，可以提前返回深度
                if(node->left == nullptr && node->right == nullptr)
                    return depth;
            }
        }
        // 
        return depth;
    }
};